home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / os2 / octa209s.zip / octave-2.09 / src / Map.cc < prev    next >
C/C++ Source or Header  |  1996-12-06  |  5KB  |  291 lines
  1. /*
  2.  
  3. Copyright (C) 1996 John W. Eaton
  4.  
  5. This file is part of Octave.
  6.  
  7. Octave is free software; you can redistribute it and/or modify it
  8. under the terms of the GNU General Public License as published by the
  9. Free Software Foundation; either version 2, or (at your option) any
  10. later version.
  11.  
  12. Octave is distributed in the hope that it will be useful, but WITHOUT
  13. ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with Octave; see the file COPYING.  If not, write to the Free
  19. Software Foundation, 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20.  
  21. */
  22.  
  23. /*
  24.  
  25. The classes in this file are derived from the old `genclass' versions
  26. of Map and CHMap from libg++, originally:
  27.  
  28.   Copyright (C) 1988 Free Software Foundation
  29.     written by Doug Lea (dl@rocky.oswego.edu)
  30.  
  31. and distributed under the terms of the GNU Library General Public
  32. License as published by the Free Software Foundation.
  33.  
  34. */
  35.  
  36. #if defined (__GNUG__)
  37. #pragma implementation
  38. #endif
  39.  
  40. #ifdef HAVE_CONFIG_H
  41. #include <config.h>
  42. #endif
  43.  
  44. #include <iostream.h>
  45.  
  46. #include "Map.h"
  47.  
  48. static unsigned int
  49. hash (const string& str)
  50. {
  51.   unsigned h = 0;
  52.   for (unsigned i = 0; i < str.length (); i++)
  53.     h = h * 33 + str[i];
  54.   return h;
  55. }
  56.  
  57. template <class C>
  58. Pix
  59. Map<C>::seek (const string& item) const
  60. {
  61.   Pix i = 0;
  62.  
  63.   for (i = first (); i != 0 && key (i) != item; next (i))
  64.     ; // Skip items until match found.
  65.  
  66.   return i;
  67. }
  68.  
  69. template <class C>
  70. int
  71. Map<C>::owns (Pix idx) const
  72. {
  73.   if (idx == 0)
  74.     return 0;
  75.  
  76.   for (Pix i = first (); i != 0; next (i))
  77.     if (i == idx)
  78.       return 1;
  79.  
  80.   return 0;
  81. }
  82.  
  83. template <class C>
  84. void
  85. Map<C>::clear (void)
  86. {
  87.   Pix i = first ();
  88.   while (i != 0)
  89.     {
  90.       del (key (i));
  91.       i = first ();
  92.     }
  93. }
  94.  
  95. template <class C>
  96. int
  97. Map<C>::contains (const string& item) const
  98. {
  99.   return seek (item) != 0;
  100. }
  101.  
  102. template <class C>
  103. void
  104. Map<C>::error (const string& msg) const
  105. {
  106.   cerr << "Map: " << msg << "\n";
  107. }
  108.  
  109. // CHMap class.
  110.  
  111. // The nodes are linked together serially via a version of a trick
  112. // used in some vtables: odd pointers are actually links to the next
  113. // table entry.  Not terrible, but not wonderful either.
  114.  
  115. template <class C>
  116. static int
  117. goodCHptr (CHNode<C> *t)
  118. {
  119.   return ((((unsigned) t) & 1) == 0);
  120. }
  121.  
  122. // This sucks, but avoids g++ 2.6.0 `type unification failed' errors.
  123.  
  124. static void *
  125. index_to_CHptr (int i)
  126. {
  127.   return (void *) ((i << 1) + 1);
  128. }
  129.  
  130. template <class C>
  131. static unsigned int
  132. CHptr_to_index (CHNode<C> *t)
  133. {
  134.   return ((unsigned) t) >> 1;
  135. }
  136.  
  137. template <class C>
  138. CHMap<C>::CHMap (const C& dflt, unsigned int sz) : Map<C> (dflt)
  139. {
  140.   tab = new CHNode<C>* [size = sz];
  141.   for (unsigned int i = 0; i < size; ++i)
  142.     tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  143.   count = 0;
  144. }
  145.  
  146. template <class C>
  147. CHMap<C>::CHMap (const CHMap& a) : Map<C> (a.def)
  148. {
  149.   tab = new CHNode<C>* [size = a.size];
  150.   for (unsigned int i = 0; i < size; ++i)
  151.     tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  152.   count = 0;
  153.   for (Pix p = a.first (); p; a.next (p))
  154.     (*this) [a.key (p)] = a.contents (p);
  155. }
  156.  
  157. template <class C>
  158. Pix
  159. CHMap<C>::seek (const string& key) const
  160. {
  161.   unsigned int h = hash (key) % size;
  162.  
  163.   for (CHNode<C> *t = tab[h]; goodCHptr (t); t = t->tl)
  164.     if (key == t->hd)
  165.       return Pix (t);
  166.  
  167.   return 0;
  168. }
  169.  
  170. template <class C>
  171. C&
  172. CHMap<C>::operator [] (const string& item)
  173. {
  174.   unsigned int h = hash (item) % size;
  175.  
  176.   CHNode<C> *t = 0;
  177.   for (t = tab[h]; goodCHptr (t); t = t->tl)
  178.     if (item == t->hd)
  179.       return t->cont;
  180.  
  181.   t = new CHNode<C> (item, def, tab[h]);
  182.   tab[h] = t;
  183.   ++count;
  184.   return t->cont;
  185. }
  186.  
  187. template <class C>
  188. void
  189. CHMap<C>::del (const string& key)
  190. {
  191.   unsigned int h = hash (key) % size;
  192.  
  193.   CHNode<C> *t = tab[h];
  194.   CHNode<C> *trail = t;
  195.   while (goodCHptr (t))
  196.     {
  197.       if (key == t->hd)
  198.     {
  199.       if (trail == t)
  200.         tab[h] = t->tl;
  201.       else
  202.         trail->tl = t->tl;
  203.       delete t;
  204.       --count;
  205.       return;
  206.     }
  207.       trail = t;
  208.       t = t->tl;
  209.     }
  210. }
  211.  
  212. template <class C>
  213. void
  214. CHMap<C>::clear (void)
  215. {
  216.   for (unsigned int i = 0; i < size; ++i)
  217.     {
  218.       CHNode<C> *p = tab[i];
  219.       tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  220.       while (goodCHptr (p))
  221.     {
  222.       CHNode<C> *nxt = p->tl;
  223.       delete p;
  224.       p = nxt;
  225.     }
  226.     }
  227.   count = 0;
  228. }
  229.  
  230. template <class C>
  231. Pix
  232. CHMap<C>::first (void) const
  233. {
  234.   for (unsigned int i = 0; i < size; ++i)
  235.     if (goodCHptr (tab[i]))
  236.       return Pix (tab[i]);
  237.   return 0;
  238. }
  239.  
  240. template <class C>
  241. void
  242. CHMap<C>::next (Pix& p) const
  243. {
  244.   CHNode<C> *t = ((CHNode<C> *) p)->tl;
  245.   if (goodCHptr (t))
  246.     p = Pix (t);
  247.   else
  248.     {
  249.       for (unsigned int i = CHptr_to_index (t); i < size; ++i)
  250.     {
  251.       if (goodCHptr (tab[i]))
  252.         {
  253.           p =  Pix (tab[i]);
  254.           return;
  255.         }
  256.     }
  257.       p = 0;
  258.     }
  259. }
  260.  
  261. template <class C>
  262. int
  263. CHMap<C>::OK (void) const
  264. {
  265.   int v = tab != 0;
  266.   int n = 0;
  267.  
  268.   for (unsigned int i = 0; i < size; ++i)
  269.     {
  270.       CHNode<C> *p = 0;
  271.  
  272.       for (p = tab[i]; goodCHptr (p); p = p->tl)
  273.     ++n;
  274.  
  275.       v &= CHptr_to_index (p) == i + 1;
  276.     }
  277.  
  278.   v &= count == n;
  279.  
  280.   if (! v)
  281.     error ("invariant failure");
  282.  
  283.   return v;
  284. }
  285.  
  286. /*
  287. ;;; Local Variables: ***
  288. ;;; mode: C++ ***
  289. ;;; End: ***
  290. */
  291.